package day01;

import java.util.Arrays;
import java.util.Random;

/**
 * @author wang hao
 * @date 2023-02-12 18:22
 *
 *  第三版快速排序 双路快速排序算法
 */
public class QuickSort3 {

    public static void sort(int[] arr){
        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int l, int r){
        if (l >= r) return;
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    public static int partition(int[] arr, int l, int r){
        // 生成 [l, r] 之间的随机索引
        int p = new Random().nextInt(r - l + 1) + l;
        swap(arr, l, p);

        // arr[l+1 , i-1] <= v   arr[j+1, r] >= v
        int i = l + 1, j = r;
        while (true){
            while (i <= j && arr[i] < arr[l]){
                i++;
            }

            while (j >= i && arr[j] > arr[l]){
                j--;
            }

            if (i >= j) break;

            swap(arr, i, j);
            i++;
            j--;
        }

        swap(arr, l, j);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }


    public static void main(String[] args) {
        int[] arr = new int[]{3,7,9,4,6,1,2,8,9,12,11};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
